#include <stdio.h>
#include <stdlib.h>

/* https://c.biancheng.net/view/3427.html */

#define keyType int
typedef struct {
    //查找表中每个数据元素的值
    keyType key;
    //如果需要，还可以添加其他属性
}ElemType;

typedef struct {
    //存放查找表中数据元素的数组
    ElemType * elem;
    //记录查找表中数据的总数量
    int length;
}SSTable;

//创建查找表
void CreateTable(SSTable **st, int length) {
    (*st) = (SSTable *)malloc(sizeof(SSTable));
    (*st)->length = length;
    (*st)->elem = (ElemType *)malloc(sizeof(ElemType) * (length + 1));
    printf("输入表中的数据元素：\n");
    //根据查找表中数据元素的总长度，在存储时，从数组下标为 1 的空间开始存储数据
    for(int i = 1; i <= length; i++) {
        scanf("%d", &((*st)->elem[i].key));
    }
}

//查找表查找的功能函数，其中key为关键字
int Search_seq(SSTable *st, keyType key) {
    //将关键字作为一个数据元素存放到查找表的第一个位置，起监视哨的作用
    st->elem[0].key = key;
    int i = st->length;
    while (st->elem[i].key != key)
    {
        /* code */
        i--;
    }
    //如果 i=0，说明查找失败；反之，返回的是含有关键字key的数据元素在查找表中的位置
    return i;    
}

int main(int argc, char * argv[]) {
    SSTable *st;
    CreateTable(&st, 6);
    getchar();
    printf("请输入查找数据的关键字：\n");
    int key;
    scanf("%d", &key);
    int location  = Search_seq(st, key);
    if(location == 0) {
        printf("查找失败\n");
    } else {
        printf("数据在查找表中的位置为：%d",location);
    }
    
    return 0;
}